/*
 * @lc app=leetcode.cn id=797 lang=java
 *
 * [797] 所有可能的路径
 */

import java.util.List;
import java.util.ArrayList;

// @lc code=start
class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(res, new ArrayList<>(), graph, 0, graph.length);
        return res;
    }

    private void dfs(List<List<Integer>> res, List<Integer> result, int[][] graph, int i, int n) {
        if(i == n-1) {
            result.add(i);
            res.add(new ArrayList<>(result));
            result.remove(result.size() - 1);
            return;
        }

        result.add(i);
        for(int next : graph[i]) {
            dfs(res, result, graph, next, n);
        }

        result.remove(result.size() - 1);
    }
}
// @lc code=end

